package leetcode.dfs;

//130. 被围绕的区域
public class Solve {

    public static void main(String[] args) {
        char[][] data=new char[][]{
                {'X','X','X','X'},
                {'X','O','O','X'},
                {'X','O','X','X'}};
      solve(data);

    }
    public static void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘o开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //这两条if语句的顺序不能变！！！！
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                if (board[i][j] == '#') {
                    //边界值以及和边界相连的值回复回去
                    board[i][j] = 'O';
                }
            }
        }
        System.out.println("------------------------");
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(board[i][j]);
            }
            System.out.println();
        }

    }

    private static void dfs(char[][] board, int x, int y) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || board[x][y] == 'X'
                //说明已经搜索过
                || board[x][y] == '#') {
            return;
        }

        board[x][y] = '#';
        int[] dx = new int[]{-1, 1, 0, 0};
        int[] dy = new int[]{0, 0, -1, 1};
        for (int i = 0; i < 4; i++) {
            int mx = x + dx[i];
            int my = y + dy[i];
            dfs(board, mx, my);
        }
    }
}
